// 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

// 你可以对一个单词进行如下三种操作：

// 插入一个字符
// 删除一个字符
// 替换一个字符

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/edit-distance
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 看了题解，动态规划

// 执行用时：
// 12 ms
// , 在所有 C++ 提交中击败了
// 77.03%
// 的用户
// 内存消耗：
// 8.9 MB
// , 在所有 C++ 提交中击败了
// 25.98%
// 的用户

class Solution {
public:
    int minDistance(string word1, string word2) {
        // dp[i][j]：word1前i变成Word2前j需要多少编辑距离
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        // 全删
        for(int i=0;i<word1.size()+1;i++){
            dp[i][0]=i;
        }
        // 全增
        for(int i=0;i<word2.size()+1;i++){
            dp[0][i]=i;
        }

        // 需要+1，因为ij代表word的长度
        for(int i=1;i<word1.size()+1;i++){
            for(int j=1;j<word2.size()+1;j++){
                // dp[i-1][j]:i-1与j相等，删除
                // dp[i][j-1]:i与j-1相等，增加
                // dp[i-1][j-1]:i-1与j-1相等，修改
                dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
                // 若相等，不用+1
                if(word1[i-1]==word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};